虚拟内存

VM 基本概念

• PA：Physical Address 物理地址，$n$$n$ 位

  • PPN：Physical Page Number 物理页号，$m-p$$m-p$ 位

  • PPO：Physical Page Offset 物理页面偏移，$p$$p$ 位

• VA：Virtual Address 虚拟地址，$m$$m$ 位

  • VPN：Virtual Page Number 虚拟页号，$n-p$$n-p$ 位

  • VPO：Virtual Page Offset 虚拟页面偏移，$p$$p$ 位

• MMU：Memory Management Unit 内存管理单元

• 地址空间：一个非负整数地址的有序集合 $\to$$\rightarrow$ 一个进程可用于寻址内存的一套地址集合

  • 线性地址空间： $\{0,1,2,···\}$$\{0,1,2,···\}$

  • VAS：虚拟地址空间 $\{0,1,2,···,N-1\},N=2^n$$\{0,1,2,···,N-1\},\ N=2^n$

  • PAS ：物理地址空间 $\{0,1,2,···,M-1\},M=2^m$$\{0,1,2,···,M-1\},\ M=2^m$

• VP：Virtual Page 虚拟页 ，大小 $P=2^p$$P=2^p$

• PP： Physical Page 物理页/页帧，大小 $P=2^p$$P=2^p$

• PTE：Page Table Entry 页表条目，页表将虚拟页映射到物理页

  • PTBR：Page Table Base Register 页表基址寄存器

  • PTEA：页表条目地址

• TLB：Translation Lookaside Buffer 快表，针对PTE的缓存，存储在MMU中

  • TLBT：TLB索引，$n-p-t$$n-p-t$ 位

  • TLBI：TLB标记，$t$$t$ 位，其中 $t$$t$ 表示TLB有 $T=2^t$$T=2^t$ 个组

• 段页式管理：分页与分段的区别

  • 页是信息的物理信息，分页的主要目的是为了实现离散分配，提高内存利用率，分页仅仅是系统管理的需求，对用户不可见。页的大小固定且由系统决定。

  • 段是信息的逻辑单位，分段的主要目的是为了更好地满足用户需求，分段对用户可见。段的长度不固定决定于用户编写的程序。

  • 分段比分页更容易实现信息的共享和保护。因为分页时一个进程不能完全装入一个页中，因此不便操作。

VM基本思想

物理寻址

虚拟寻址

• MMU将代码和数据的虚拟地址映射成实际系统中的物理地址。

  • 这种转换是在硬件中自动进行的，对应用程序是透明的。

• 除了地址转换外，MMU还控制内存访问权限、内存排序和每个区域内存的缓存策略。

VM意义

VM作为工具

期望：足够快的，足够大的，私有的

1. 它将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式，它高效地使用了主存。

2. 它为每个进程提供了一致的地址空间，从而简化了内存管理。

3. 它保护了每个进程的地址空间不被其他进程破坏。

VM作为缓存的工具

1. Memory hierarchy

2. DRAM硬件组织结构

1. 内存是磁盘的缓存

   1. 在VM的惯用说法中，页——缓存块，交换/页面调度——传送块

   2. 物理页在内存中，虚拟页在磁盘中

   3. 采用按需页面调度的方式

2. DRAM缓存是全相联的，任意物理页都可以包含任意虚拟页

虚拟页

在任意时刻，虚拟页面的集合都分为三个不相交的子集：

• 未分配的：VM 系统还未分配（或者创建）的页。

  • 未分配的块没有任何数据和它们相关联，因此也就不占用任何磁盘空间。

• 缓存的：当前已缓存在物理内存中的已分配页。

• 未缓存的：未缓存在物理内存中的已分配页

页表

页表结构

1. 抽象地，假定PTE由一个有效位和一个n位地址字段组成的

   

2. 具体地，x86的页表项组成

   • x86-32

     

   • x86-64

     

     

页命中

缺页

Waiting until the miss to copy the page to DRAM is known as demand paging.(按需页面调度)

替换策略

分配页面

效率保证

VM作为内存管理的工具

操作系统位每个进程提供一个独立的页表，也即一个独立的虚拟地址空间

• 简化链接：内存映像基本格式的一致性，允许链接器生成独立于物理内存的完全链接的可执行文件

• 简化加载：加载器只分配虚拟页，只有初次被引用时才将数据复制到内存中

• 简化共享：将不同进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享这部分代码的一个副本

• 简化内存分配：由于页表的工作方式，要求额外分配内存时，分配连续k个虚拟页，并映射到任意k个物理页

VM作为内存保护的工具

• 直接利用PTE实现内存保护

• 四个许可位

  • SUP：是否必须运行内核模式才能访问该页

  • READ：可读

  • WRITE：可写

  • EXEC：可执行

• 一般保护故障：Linux报告为 Segmentation fault

地址翻译

符号表

考虑一个有SRAM高速缓存和VM的系统

宏观理解

1. 物理地址直接访问Disk

2. 物理地址访问+MM作为Disk的缓存

3. 物理地址访问+Cache作为MM的缓存+MM作为Disk的缓存

4. 虚拟地址访问+地址翻译+Cache作为MM的缓存+MM作为Disk的缓存

微观理解

页表

• 基本步骤

  1. $VA=VPN+VPO$$VA = VPN+VPO$

  2. $PTBR+VPN=PTEA$$PTBR+VPN=PTEA$

  3. $PTEA$$PTEA$ 访问页表得到 $PTE$$PTE$（无论hit/miss）

  4. $MMU$$MMU$ 处理 $PTE$$PTE$ 得到 $PPN$$PPN$

  5. $PPN+VPO=PPN+PPO=PA$$PPN+VPO=PPN+PPO=PA$

• PTE hit：存在物理页缓存了该虚拟页，即MM中有Disk的缓存

  

• PTE miss：不存在物理页缓存了该虚拟页，触发page fault更新MM中的物理页（该过程对地址翻译隐藏）

  

页表+Cache

• 基本步骤不变，Cache实现所有数据的缓存（该过程对地址翻译隐藏）

• 细节注意：

  • Cache分别存储PTE和Data（Data的高速缓存使用物理寻址），因而不会破坏地址翻译的基本流程

  • 否则，若Data的高速缓存直接使用虚拟寻址，跳过地址翻译，则需要高速缓存额外处理访问权限等保护问题

页表+TLB+Cache

• 基本步骤

  1. $VA=VPN+VPO$$VA = VPN+VPO$

  2. $VPN$$VPN$ 访问 $TLB$$TLB$ 得到 $PTE$$PTE$（无论hit/miss）

  3. $MMU$$MMU$ 处理 $PTE$$PTE$ 得到 $PPN$$PPN$

  4. $PPN+VPO=PPN+PPO=PA$$PPN+VPO=PPN+PPO=PA$

• TLB hit：TLB中缓存了该VPN对应的PTE，所有地址翻译都在MMU中快速实现

  

• TLB miss：MMU访问L1 Cache取出相应的PTE

  

   

多级页表+TLB+Cache

• 基本步骤

  1. $VA=\sum VP{N}_i+VPO$$VA = \sum VPN_i+VPO$

  2. $VPN$$VPN$ 访问 $TLB$$TLB$ 得到 $PTE$$PTE$（无论hit/miss）

  3. $MMU(TWU)$$MMU(TWU)$ 处理 $PTE$$PTE$ 得到 $PPN$$PPN$

  4. $PPN+VPO=PPN+PPO=PA$$PPN+VPO=PPN+PPO=PA$

• 多级页表

  

• TWU：Table Walking Unit

  

• 例子：64位系统，$9+9+9+9+12=48$$9+9+9+9+12=48$

  

翻译细节

Cache

设计$PPO=CI+CO$$PPO=CI+CO$，使得在借由 $VPN$$VPN$ 获取 $PPN$$PPN$ 时，可以同步利用 $VPO$$VPO$ 对cache进行查找

TLB

1. 虚拟地址中用以访问TLB的组成部分

   

2. TLB结构：8路组相连的命中率几乎和全相连命中率几乎一样

3. TLB存储：Contains complete page table entries for small number of pages

页面大小

1. 小页面的优点

   • 内部碎片：随便选择一个数据段、堆栈段很可能不会恰好装满整数个页面，平均有一半为空

   • 运行小型程序时，对于内存的占用较少

2. 小页面的缺点

   • 小页面，意味着需要更多的页面和更大的页表：存储空间+传输时间

   • 对TLB不友好：小页表意味着地址转换时需要更多的页表映射表项，意味着TLB缓存的表项多，降低TLB的命中率；

3. 只考虑碎片浪费和页表所需的内存

   

例子：内存系统

简易例子

Core i7

系统结构

• 48 位虚拟地址空间，52 位物理地址空间

  • 地址翻译过程中可用的地址空间是 48 位（实际是 47，因为任何虚拟地址的 48 位至 63 位必须与第 47 位相同）

• 所有 TLB 均为 4 路组相联，以虚拟地址访问

• L1 d-TLB、L1 i-TLB、L2 unified TLB 分别有 64、128、512 个页表项

• 单核内所有 Cache 均为 8 路组相联，物理地址访问

• L1 d-cache、L1 i-cache、L2 unidifed cache 大小分别为 32KB、32KB、256KB

• 多核共享 L3 Cache，16 路组相联，大小为 8MB

• Core i7 要求页大小为 4KB 或 4MB

• Linux 页表大小总为 4 KB（12 位）

地址翻译

PTE结构

前三级

• P：子页表在/不在物理内存

• R/W: 所有可访问页的只读或读写权限

• U/S: 所有可访问页的用户或超级用户（内核）访问权限

• WT：子页表直写/写回缓存策略

• CD：能/不能缓存子页表

• A: 引用位（每次访问都会设置，可以用它实现页替换算法）

• PS：4KB 或 4MB 页大小（只对第一层PTE定义）

• Base addr：子页表物理地址的高 40 位（物理页表 4KB 对齐）

• XD：能/不能从这个 PTE 可访问的所有页中取指令

第四级

• P：子页在/不在物理内存

• R/W: 子页的只读或读写权限

• U/S: 子页的用户或超级用户（内核）访问权限

• WT：子页直写/写回缓存策略

• CD：能/不能缓存子页

• A: 引用位（每次访问都会设置，可以用它实现页替换算法）

• D: 修改位（写后设置，决定是否写回牺牲页）

• G: 全局位（任务切换时，不从 TLB 中驱逐出去）

• Base addr：子页物理地址的高 40 位（物理页 4KB 对齐）

• XD：能/不能从这个子页中取指令

内存管理

• 每个进程共享内核代码和全局数据

• 页表和内核在进程的上下文运行代码时使用的栈等每个进程不同

• Linux 将物理内存完整地映射到内核虚拟内存的一段连续页，方便访问物理内存

虚拟内存区域

• 每个进程有一个 task_struct

  • 包含 PID、指向用户栈的指针、可执行目标文件的名字、以及程序计数器等

• pgd： 指向第一级页表（页全局目录）的基址

• mmap： 指向一个 vm_area_structs（区域结构）的链表

• vm_start：指向这个区域的起始处

• vm_end：指向这个区域的结束处

• vm_prot：描述这个区域内包含的所有页的读写许可权限

• vm_flags：描述这个区域内的页面是与其他进程共享的，还是这个进程私有的（还描述了其他一些信息）

• vm_next：指向链表中下一个区域结构。

缺页异常处理

1. 地址是否存在：是否在某个段内

2. 访问是否合法：查看读/写/执行位

3. 否则，缺页导致：将页面调入

内存映射

交换空间

相关函数

• fork和execve

• mmap和munmap

动态内存分配

• DMA：动态内存分配器，对虚拟内存进行管理

显示分配器

基本实现

函数实现

• 分配

xxxxxxxxxx
1
1
void *malloc(size_t size);  //成功：返回已分配块的指针；错误：NULL

• （双字）对齐原则

  • 32位：地址总是8的倍数

  • 64位：地址总是16的倍数

  • 堆假设块是8字节双字边界对齐的

• 不初始化所返回的内存

  • calloc：Version of malloc that initializes allocated block to zero

    xxxxxxxxxx
    1
    1
    void *calloc(size_t n, size_t size);
    

  • realloc：Changes the size of a previously allocated block

    xxxxxxxxxx
    1
    1
    void realloc(void *tr, size_t new_size);
    

  • sbrk：Used internally by allocators to grow or shrink the heap

    xxxxxxxxxx
    1
    1
    void *sbrk(intptr_t incr); //Returns: old brk pointer on success, −1 on error
    

• 回收

xxxxxxxxxx
1
1
void free(void *ptr); //Returns: nothing

要求

1. 处理任意请求序列

2. 立即响应请求

3. 只使用堆

4. 对齐块（对齐要求）

5. 不修改已分配的块

目标

1. 最大化呑吐率

2. 最大化内存利用率

碎片

1. 内部碎片：已分配块比有效载荷大

2. 外部碎片：空闲内存合计可满足分配请求，但单独空闲块不够

问题

1. 空闲块组织：我们如何记录空闲块？

2. 放置：我们如何选择一个合适的空闲块来放置一个新分配的块？

3. 分割：在将一个新分配的块放置到某个空闲块之后，我们如何处理这个空闲块中的剩余部分？

4. 合并：我们如何处理一个刚刚被释放的块？

隐式空闲链表

基本结构

1. 堆块格式

   

   xxxxxxxxxx
   5
   1
   typedef struct block
   2
   {
   3
       word_t header;
   4
       unsigned char payload[0]; //Zero length array
   5
   } block_t;
   

    

2. 组织形式

   

3. 分割空闲块

   

4. 获取额外的堆内存

放置策略

合并空闲块

1. 合并的概念

   • 当分配器释放一个已分配块时，可能有其他空闲块与这个新释放的空闲块相邻。这些邻接的空闲块可能引起一种现象，叫做假碎片（fault fragmentation）

   • 任何实际的分配器都必须合并相邻的空闲块，这个过程称为合并（coalescing）

2. 合并策略

   • 立即合并（immediate coalescing）

   • 推迟合并（deferred coalescing）

3. 边界标记实现

   

   • 考虑当分配器释放当前块时所有可能存在的情况：

     

   

4. 边界标记优化：只有空闲块需要尾部

   

   

显式空闲链表

1. 块结构

   

2. 组织方式：双向空闲链表

3. 排序策略

   

分离空闲链表

简单分离存储

分离适配

伙伴系统

隐式分配器